πŸ“‚ Heap

@Seongukbaek Posted May 21, 2022 Β· Updated May 21, 2022 Β· 4 min read

🧷 νž™(Heap)

μš°μ„ μˆœμœ„ 큐λ₯Ό μœ„ν•΄ λ§Œλ“€μ–΄μ§„ μžλ£Œκ΅¬μ‘°μ΄λ‹€.

  • μ‚½μž…κ³Ό μ‚­μ œ λͺ¨λ‘ O(logN)O(logN)으둜 ν•΄κ²°ν•  수 μžˆλ‹€.
  • μ™„μ „ 이진 트리의 일쒅이닀.

    • μ—¬λŸ¬ κ°’ 쀑, μ΅œλŒ“κ°’κ³Ό μ΅œμ†Ÿκ°’μ„ λΉ λ₯΄κ²Œ 찾아내도둝 λ§Œλ“€μ–΄μ§„ 자료ꡬ쑰
  • 반 μ •λ ¬ μƒνƒœ (무쑰건 μ •λ ¬λ˜μ–΄ μžˆμ„ ν•„μš”κ°€ μ—†λ‹€.)
  • νž™ νŠΈλ¦¬λŠ” μ€‘λ³΅λœ κ°’ ν—ˆμš© (이진 탐색 νŠΈλ¦¬λŠ” 쀑볡값을 ν—ˆμš©ν•˜μ§€ μ•ŠμŒ)

μš°μ„ μˆœμœ„ 큐? : μš°μ„ μˆœμœ„μ˜ κ°œλ…μ„ 큐에 λ„μž…ν•œ 자료ꡬ쑰둜, 데이터듀이 μš°μ„ μˆœμœ„λ₯Ό κ°€μ§€κ³  있고 이에 따라 μš°μ„ μˆœμœ„κ°€ 높은 데이터가 λ¨Όμ € λ‚˜κ°€κ²Œ λ˜λŠ” ꡬ쑰이닀.

  • μš°μ„ μˆœμœ„ νλŠ” λ°°μ—΄, μ—°κ²°λ¦¬μŠ€νŠΈ, νž™μœΌλ‘œ κ΅¬ν˜„ν•  수 μžˆλŠ”λ°, κ·Έ 쀑 νž™μ΄ κ°€μž₯ νš¨μœ¨μ μ΄λ‹€.

μ™„μ „ 이진 트리? : λ…Έλ“œλ₯Ό μ‚½μž…ν•  λ•Œ, μ™Όμͺ½λΆ€ν„° μ°¨λ‘€λŒ€λ‘œ μ‚½μž…ν•˜λŠ” νŠΈλ¦¬μ΄λ‹€.

πŸͺš μ’…λ₯˜

μ΅œλŒ€ νž™(Max Heap)

  • λΆ€λͺ¨ λ…Έλ“œμ˜ ν‚€ 값이 μžμ‹ λ…Έλ“œμ˜ ν‚€ 값보닀 ν¬κ±°λ‚˜ 같은 μ™„μ „ 이진 트리

μ΅œμ†Œ νž™(Min Heap)

  • λΆ€λͺ¨ λ…Έλ“œμ˜ ν‚€ 값이 μžμ‹ λ…Έλ“œμ˜ ν‚€ 값보닀 μž‘κ±°λ‚˜ 같은 μ™„μ „ 이진 트리

πŸͺš κ΅¬ν˜„

νž™μ„ μ €μž₯ν•˜λŠ” ν‘œμ€€μ  μžλ£Œκ΅¬μ‘°λŠ” λ°°μ—΄ 이닀.

  • κ΅¬ν˜„μ„ μ‰½κ²Œ ν•˜κΈ° μœ„ν•΄ λ°°μ—΄μ˜ 첫 번째 인덱슀인 0은 μ‚¬μš©λ˜μ§€ μ•ŠλŠ”λ‹€.
  • νŠΉμ • μœ„μΉ˜μ˜ λ…Έλ“œ λ²ˆν˜ΈλŠ” μƒˆλ‘œμš΄ λ…Έλ“œκ°€ μΆ”κ°€λ˜μ–΄λ„ λ³€ν•˜μ§€ μ•ŠλŠ”λ‹€.

λΆ€λͺ¨ λ…Έλ“œμ™€ μžμ‹ λ…Έλ“œμ˜ 관계

μ™Όμͺ½ μžμ‹ index = (λΆ€λͺ¨ index) * 2 였λ₯Έμͺ½ μžμ‹ index = (λΆ€λͺ¨ index) * 2 + 1 λΆ€λͺ¨ index = (μžμ‹ index) / 2

μ‚½μž…

  1. νž™μ— μƒˆλ‘œμš΄ μš”μ†Œκ°€ λ“€μ–΄μ˜€λ©΄, 일단 μƒˆλ‘œμš΄ λ…Έλ“œλ₯Ό νž™μ˜ λ§ˆμ§€λ§‰ λ…Έλ“œμ— μ‚½μž…
  2. μƒˆλ‘œμš΄ λ…Έλ“œλ₯Ό λΆ€λͺ¨ λ…Έλ“œλ“€κ³Ό κ΅ν™˜
// μ΅œλŒ€ νž™μ˜ μ‚½μž… κ΅¬ν˜„ void insertMaxHeap(int x) { // νž™ 크기λ₯Ό μ¦κ°€μ‹œν‚€κ³ , λ§ˆμ§€λ§‰ λ…Έλ“œμ— μ‚½μž… maxHeap[++heapSize] = x; for (int i = heapSize; i > 1; i/=2) { // λ§ˆμ§€λ§‰ λ…Έλ“œκ°€ μžμ‹ μ˜ λΆ€λͺ¨ λ…Έλ“œλ³΄λ‹€ 크면 swap if (maxHeap[i/2] < maxHeap[i]) swap(i/2, i); else break; } }

μ‚­μ œ

  1. μ΅œλŒ€ νž™μ—μ„œ μ΅œλŒ“κ°’μ€ 루트 λ…Έλ“œμ΄λ―€λ‘œ 루트 λ…Έλ“œκ°€ μ‚­μ œλ¨
  2. μ‚­μ œλœ 루트 λ…Έλ“œμ—λŠ” νž™μ˜ λ§ˆμ§€λ§‰ λ…Έλ“œλ₯Ό κ°€μ Έμ˜΄
  3. νž™μ„ μž¬κ΅¬μ„±(heapify)
// μ΅œλŒ€ νž™ μ‚­μ œ κ΅¬ν˜„ int deleteMaxHeap() { if (heapSize == 0) return 0; // 루트 λ…Έλ“œμ˜ 값을 μ €μž₯ν•˜κ³ , λ§ˆμ§€λ§‰ λ…Έλ“œ 값을 루트둜 μ΄λ™ν•œ ν›„ νž™ 크기λ₯Ό 쀄여 λ§ˆμ§€λ§‰ λ…Έλ“œλ₯Ό 0으둜 μ΄ˆκΈ°ν™” int item = maxHeap[1]; maxHeap[1] = maxHeap[heapSize]; maxHeap[heapSize--] = 0; for (int i = 1; i*2 <= heapSize;) { // λ§ˆμ§€λ§‰ λ…Έλ“œκ°€ μ™Όμͺ½ λ…Έλ“œμ™€ 였λ₯Έμͺ½ λ…Έλ“œλ³΄λ‹€ 크면 μ΅œλŒ€ νž™μ΄λ―€λ‘œ μ’…λ£Œ if (maxHeap[i] > maxHeap[i*2] && maxHeap[i] > maxHeap[i*2+1]) break; // μžμ‹ λ…Έλ“œκ°€ 더 큰 경우, κ΅ν™˜ν•œ ν›„, iλ₯Ό λ³€κ²½ else if (maxHeap[i*2] > maxHeap[i*2+1]) { swap(i, i*2); i *= 2; } else { swap(i, i*2+1); i = i*2+1; } } return item; }

πŸ“• μ°Έκ³ 

@Seongukbaek
배우고 μ •λ¦¬ν•˜κ³  κ³΅μœ ν•˜λŠ” λŒ€ν•™μƒ λ°±μ„±μš±μž…λ‹ˆλ‹€ πŸ˜€